|
In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets ''A'' and ''B'' of natural numbers, is it possible to effectively convert a method for deciding membership in ''B'' into a method for deciding membership in ''A''? If the answer to this question is affirmative then ''A'' is said to be reducible to ''B''. The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set ''A'' then ''A'' must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable. == Reducibility relations== A reducibility relation is a binary relation on sets of natural numbers that is * Reflexive: Every set is reducible to itself. * Transitive: If a set ''A'' is reducible to a set ''B'' and ''B'' is reducible to a set ''C'' then ''A'' is reducible to ''C''. These two properties imply that a reducibility is a preorder on the powerset of the natural numbers. Not all preorders are studied as reducibility notions, however. The notions studied in computability theory have the informal property that ''A'' is reducible to ''B'' if and only if any (possibly noneffective) decision procedure for ''B'' can be effectively converted to a decision procedure for ''A''. The different reducibility relations vary in the methods they permit such a conversion process to use. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Reduction (recursion theory)」の詳細全文を読む スポンサード リンク
|